package com.markedquilt.Interview;
/*
 * PackageName: com.markedquilt.Interview
 * ClassName:   waysToStep
 * Author:   zhang
 * Date:     Created in 2020/10/21
 * Description:
 * History:
 * <author>        <time>             <version>          <desc>
 * 作者姓名         修改时间            版本号              描述
 * zhang           2020/10/21      1.0
 */

/**
 * Title:
 * Project: LeetcodeProblem
 *
 * @author ZhangKe
 * Created on 2020/10/21
 */
//array[0,1,2,4]
//array[4]=dp[3]+dp[2]*dp[2]+dp[1]*dp[3]
//array[n]=dp[n-1]+dp[n-2]*dp[2]+dp[n-3]*dp[3]......
public class num0801_waysToStep {
    public static int waysToStep(int n) {
        long result=0;
        if (n==1)
            return 1;
        else if (n==2)
            return 2;
        else{
            long one=1,two=2,three=4;
            result = three;
            long temp;
            for (int i = 4; i <= n; i++) {
                result = (one+two+three)%1000000007;
                temp = two;
                two =three;
                three = result;
                one = temp;
            }
            return (int)result;
        }
    }

    public static void main(String[] args) {
        System.out.println(waysToStep(4));
    }
}
